package com.xyhuo.leetcode.december;

import java.util.ArrayList;
import java.util.List;

/**
 * 插入区间
 * https://leetcode.cn/problems/insert-interval/
 *
 * @time 2023/12/25
 */
public class Insert {

//    public static void main(String[] args) {
////        int[][] intervals = {{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}};
////        int[] newInterval = {4, 8};
//
////        int[][] intervals = {{3, 5}, {12, 15}};
////        int[] newInterval = {6, 6};
//
//        int[][] intervals = {{1, 5}};
//        int[] newInterval = {0, 3};
//
//        Insert insert = new Insert();
//        insert.insert(intervals, newInterval);
//    }

    public int[][] insert(int[][] intervals, int[] newInterval) {

        boolean find = false;
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            if ((i == 0 && newInterval[1] < intervals[0][0])
                    || (i >= 1 && newInterval[0] > intervals[i - 1][1] && newInterval[1] < intervals[i][0])) {
                list.add(newInterval);
                find = true;
            }

            if (newInterval[0] > intervals[i][1] || newInterval[1] < intervals[i][0]) {
                list.add(intervals[i]);
            } else {
                int left = Math.min(intervals[i][0], newInterval[0]);

                while (true) {
                    if (i + 1 >= intervals.length || newInterval[0] > intervals[i + 1][1] || newInterval[1] < intervals[i + 1][0]) {
                        break;
                    }
                    i++;
                }
                int right = Math.max(intervals[i][1], newInterval[1]);
                int[] tmp = new int[2];
                tmp[0] = left;
                tmp[1] = right;
                list.add(tmp);
                find = true;
            }
        }
        if (!find) {
            list.add(newInterval);
        }
        int[][] ans = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }

}
